import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;


public class Utils {


	
	public static BigInteger maxBig(BigInteger[] list) {
		//System.out.println(list[0]);
		BigInteger max = BigInteger.valueOf(-9999999);
		for (BigInteger n : list) {
			if (n.compareTo(max) > 0) {
				max = n;
			}
		}
		return max;
	}
	
	
	public static Integer max(Integer[] list) {
		Integer max = -999999999;
		for (Integer n : list) {
			if (n > max) {
				max = n;
			}
		}
		return max;
	}
	
	

	public static Integer  maxIndex(Integer[] list) {
		Integer max = -9999999;
		Integer index = -1;
		for (int i=0;i<list.length;i++) {
			Integer n = list[i];
			if (n > max) {
				max = n;
				index = i;
			}
		}
		return index;
	}
	
	
	public static Long  maxIndexBig(BigInteger[] list) {
		BigInteger max = BigInteger.valueOf(-999999999);
		Long index = Long.valueOf(-1);
		for (int i=0;i<list.length;i++) {
			BigInteger n = list[i];
			if (n.compareTo(max) > 0) {
				max = n;
				index = (long)i;
			}
		}
		return index;
	}
	
	
	public static void printMatrix(Integer[][] aMatrix, String v, String w) {
		System.out.print("           ");
		for (int i=0;i<w.length();i++) {
			System.out.print(w.charAt(i)+ "   ");
		}
		System.out.println("");
		for (int i=0;i< aMatrix.length;i++) {
			Integer[] row = aMatrix[i];
			//System.out.print(" ");
			if (i > 0) {
				System.out.print(v.charAt(i-1) + "   ");
			} else {
				System.out.print("    ");
			}
			for (int j=0;j<row.length;j++) {
				Integer r = row[j];
				if (r >= 10 || r <0) {
					System.out.print("  " + row[j]);
				} else {
					System.out.print("   " + row[j]);
				}	
			}
			System.out.println("");
		}		
	}
	
	

	public static void writeFile(String text, String file) {
		Writer writer = null;

		try {
			writer = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream(file), "utf-8"));
			writer.write(text);
		} catch (IOException ex) {
			// report
		} finally {
			try {writer.close();} catch (Exception ex) {}
		}
	}



	public static ArrayList<String> readLines(String aFilePath) {
		ArrayList<String> lines = new ArrayList<String>();
		try {
			BufferedReader br = new BufferedReader(new FileReader(aFilePath));
			for(String line; (line = br.readLine()) != null; ) {	
				lines.add(line);				
			}
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return lines;

	}


	public static ArrayList<String> 
	getNodes(HashMap<String,ArrayList<String>> aGraph) {

		return null;

	}


	public static HashMap<String,ArrayList<String>> cloneGraph(
			HashMap<String,ArrayList<String>> aGraph) {
		HashMap<String,ArrayList<String>> map = 
				new HashMap<String,ArrayList<String>>();
		for(Entry<String, ArrayList<String>> entry : aGraph.entrySet())  {
			ArrayList<String> outgoings = (ArrayList<String>) entry.getValue().clone();
			map.put(entry.getKey(), outgoings);

		}
		return map;
	}


	public static HashMap<String,Integer> getInDegree(HashMap<String,ArrayList<String>> aGraph) {
		HashMap<String,Integer> inDegreeMap = new HashMap<String,Integer>(); 
		for (Entry<String,ArrayList<String>> entry : aGraph.entrySet()) {
			ArrayList<String> outgoings = entry.getValue();
			for (String outgoing : outgoings) {
				Integer indegree = inDegreeMap.get(outgoing);
				if (indegree == null) {
					inDegreeMap.put(outgoing, 1);
				} else {
					inDegreeMap.put(outgoing, indegree + 1);
				}
			}
		}
		// nodes with in-degree equals 0
		for (Entry<String,ArrayList<String>> entry : aGraph.entrySet()) {
			String key = entry.getKey();
			if (!inDegreeMap.containsKey(key)) {
				inDegreeMap.put(key, 0);
			}
		}		

		return inDegreeMap;		
	}

	public static HashMap<String,ArrayList<String>> getIngoingGraph(
			HashMap<String,ArrayList<String>> aGraph) {
		HashMap<String,ArrayList<String>> ingoingMap = 
				new HashMap<String,ArrayList<String>>();
		for (Entry<String,ArrayList<String>> entry : aGraph.entrySet()) {
			ArrayList<String> outgoings = entry.getValue();
			for (String outgoing : outgoings) {
				Utils.addElement(ingoingMap, outgoing, entry.getKey());
			}			
		}
		return ingoingMap;
	}


	public static HashMap<String,Integer> readGraphWeights(String aFilePath) {
		HashMap<String,Integer> weights = 
				new HashMap<String,Integer>();
		try {
			BufferedReader br = new BufferedReader(new FileReader(aFilePath));
			for(String line; (line = br.readLine()) != null; ) {	
				String[] splitted = line.split("->");
				String origin = splitted[0];				
				String dest = splitted[1].split(":")[0];
				Integer weight = Integer.valueOf(splitted[1].split(":")[1]);
				weights.put(origin+ "_" + dest,weight);			
			}
			br.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return weights;
	}


	public static HashMap<String,ArrayList<String>> 
	readWeightedGraph(String aFilePath) {

		HashMap<String,ArrayList<String>> graph = 
				new HashMap<String,ArrayList<String>>(); 
		try {
			BufferedReader br = new BufferedReader(new FileReader(aFilePath));
			for(String line; (line = br.readLine()) != null; ) {	
				String[] splitted = line.split("->");
				String origin = splitted[0];			
				Utils.addElement(graph, origin, splitted[1].replaceAll(":.*", ""));

			}
			br.close();
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return graph;	
	}


	public static void addElement(HashMap<String,ArrayList<String>> aMap,
			String aKey,String aNewElement) {
		ArrayList<String> list = aMap.get(aKey);
		if (list == null) {
			list = new ArrayList<String>();
			list.add(aNewElement);
			aMap.put(aKey, list);
		} else {
			list.add(aNewElement);
		}		
	}


	public static ArrayList<String> getNodesWithNoIncoming(
			HashMap<String,ArrayList<String>> aGraph){
		ArrayList<String> nodes = new ArrayList<String>();
		HashMap<String,Integer> inDegreeMap = Utils.getInDegree(aGraph);
		for (Entry<String,Integer> entry : inDegreeMap.entrySet()) {
			if (entry.getValue() == 0) {
				nodes.add(entry.getKey());
			}
		}
		return nodes;		
	}

	public static void removeFromGraph(HashMap<String,ArrayList<String>> aGraph,
			String origin, String dest) {
		ArrayList<String> outgoings = aGraph.get(origin);
		if (outgoings == null) {
			return;
		} else {
			outgoings.remove(dest);
			if (outgoings.size() == 0) {
				aGraph.remove(origin);
			}
		}
	}

	
	
	public static BigInteger[][] readMatrixBig(String aFilePath) {		
		ArrayList<ArrayList<BigInteger>> matrix = 
				new ArrayList<ArrayList<BigInteger>>();
		try {
			Scanner input = new Scanner(new File(aFilePath));
			while (input.hasNextLine()){			
				String[] line = input.nextLine().split("\\s+");		
				ArrayList<BigInteger> row = new ArrayList<BigInteger>();
				for (String s : line) {
					row.add(BigInteger.valueOf( Long.valueOf(s)  ));
				}
				matrix.add(row);
			}
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
		return Utils.convertToMatrixBig(matrix);
	}
	
	public static int[][] readMatrixInt(String aFilePath) {		
		ArrayList<ArrayList<Integer>> matrix = 
				new ArrayList<ArrayList<Integer>>();
		try {
			Scanner input = new Scanner(new File(aFilePath));
			while (input.hasNextLine()){			
				String[] line = input.nextLine().split("\\s+");		
				ArrayList<Integer> row = new ArrayList<Integer>();
				for (String s : line) {
					row.add(Integer.valueOf(s));
				}
				matrix.add(row);
			}
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
		return Utils.convertToMatrixInt(matrix);
	}
	
	
	public static Integer[][] readMatrix(String aFilePath) {		
		ArrayList<ArrayList<Integer>> matrix = 
				new ArrayList<ArrayList<Integer>>();
		try {
			Scanner input = new Scanner(new File(aFilePath));
			while (input.hasNextLine()){			
				String[] line = input.nextLine().split("\\s+");		
				ArrayList<Integer> row = new ArrayList<Integer>();
				for (String s : line) {
					row.add(Integer.valueOf(s));
				}
				matrix.add(row);
			}
		} catch (NumberFormatException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
		return Utils.convertToMatrix(matrix);
	}

	public static Integer[][] 
			convertToMatrix(ArrayList<ArrayList<Integer>> matrix) {		
		Integer n = matrix.size();
		Integer m = matrix.get(0).size();
		Integer[][] matArray = new Integer[n][m];		
		for (int i=0;i<matrix.size();i++) {
			ArrayList<Integer> row = matrix.get(i);
			for (int j=0;j<row.size();j++) {
				matArray[i][j] = row.get(j);
			}
		}
		return matArray;		
	}

	
	
	public static int[][] 
			convertToMatrixInt(ArrayList<ArrayList<Integer>> matrix) {		
		int n = matrix.size();
		int m = matrix.get(0).size();
		int[][] matArray = new int[n][m];		
		for (int i=0;i<matrix.size();i++) {
			ArrayList<Integer> row = matrix.get(i);
			for (int j=0;j<row.size();j++) {
				matArray[i][j] = row.get(j);
			}
		}
		return matArray;		
	}
	

	public static BigInteger[][] 
			convertToMatrixBig(ArrayList<ArrayList<BigInteger>> matrix) {		
		Integer n = matrix.size();
		Integer m = matrix.get(0).size();
		BigInteger[][] matArray = new BigInteger[n][m];		
		for (int i=0;i<matrix.size();i++) {
			ArrayList<BigInteger> row = matrix.get(i);
			for (int j=0;j<row.size();j++) {
				matArray[i][j] = row.get(j);
			}
		}
		return matArray;		
	}
	
	
	

}
